package nowcoder;

/**
 * JZ36 二叉搜索树与双向链表
 * https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
 */
public class 二叉搜索树与双向链表 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null){
            return null;
        }
        TreeNode leftHead = Convert(pRootOfTree.left);//一定要递归的去找他的左边关系
        TreeNode leftTail = leftHead;

        while (leftTail != null && leftTail.right != null){
            //这个只是为了找到左边的最后一个节点做处理用来连接待处理节点
            //注意这个很妙，当他变成链表的时候最左端就会有右边节点，这个可以找到链表的最后一个节点
            leftTail = leftTail.right;
        }
        if (leftTail != null){//把左边与待处理节点相连
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        TreeNode rightHead = Convert(pRootOfTree.right);//递归处理找到每个右端的待处理节点pRootOfTree
        if (rightHead != null){//有端与待处理节点相连
            rightHead.left = pRootOfTree;
            pRootOfTree.right = rightHead;
        }
        return leftHead == null ? pRootOfTree : leftHead;
    }
}
